package com.yao.sort;

/**
 * @Author: yaoym
 * @Description: 快速排序
 * @Date: Created in 14:54 2019/2/11
 * @Modified By: yaoym
 */
public class QuickDemo {

    /**
     * 1.将数组根据中轴划分为二
     * 2.递归划分后的低位数组和高位数组
     * @param arr
     * @param up
     */
    public static void quickSort(Integer[] arr, boolean up){
        //将数组一分为二
        quick(arr, 0, arr.length - 1, up);
    }

    private static int getMiddle(Integer[] arr, int low, int high, boolean up){
        int temp = arr[low];

        while(low < high){
            //找出低位比高位大的数，并交换
            while(low < high && (up ? arr[high] >= temp : arr[high] <= temp)){
                high--;
            }
            arr[low] = arr[high];

            //找出低位比高位小的数，并交换

            while(low < high && (up ? arr[low] <= temp : arr[low] >= temp)){
                low++;
            }
            arr[high] = arr[low];
            arr[low] = temp;
        }
        return low;
    }


    private  static void quick(Integer[] arr, int low, int high, boolean up){
        if(low < high){
            int middle = getMiddle(arr, low, high, up);
            quick(arr, low, middle - 1, up);
            quick(arr, middle + 1, high, up);
        }
    }


    public static void main(String[] args) {
        Integer[] arr = InitData.sortData(10);

        System.out.println("--快速排序前--");
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();

        quickSort(arr, false);

        System.out.println("--快速排序后--");
        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }
}
